#include <stdio.h>
#include <stdlib.h>

/*
 * 克鲁斯卡尔：最小生成树
 */

#define vertex 6
#define edge 10

struct edgeset
{
  int fromvex;
  int endvex;
  int weight;
};

struct tree
{
  struct edgeset c[vertex];	// 存放树的边
  struct edgeset ge[edge+1];	// 存放网中所有边
  int s[vertex+1][vertex+1];	// s为一个集合，一行原素s[i][0] ~ s[i][n]表示一个集合。
								// 若s[i][t] = 1，则表示顶点t属于该集合，否则不属于
};

void kruska(struct tree * tree)
{
  int i, j;
  int k = 1;	// 统计树的边数
  int d = 1;	// 表示待扫描边的下标位置
  int m1, m2;	// 记录一条边的两个顶点所在集合的序号

  for (i = 1; i <= vertex; i++)
    for (j = 1; j <= vertex; j++)
      if (i == j)
	tree->s[i][j] = 1;
      else
	tree->s[i][j] = 0;

  while (k < vertex) {
    for (i = 1; i <= vertex; i++)
      for (j = 1; j <= vertex; j++) {
	if ((tree->ge[d].fromvex == j) && (tree->s[i][j] == 1))
	    m1 = i;
	
	if ((tree->ge[d].endvex == j) && (tree->s[i][j] == 1))
	  m2 = i;	
      }

    if (m1 != m2) {
      tree->c[k] = tree->ge[d];
      k++;
      
      for (j = 1; j <= vertex; j++) {
	tree->s[m1][j] = tree->s[m1][j] || tree->s[m2][j];	// 求出一条边后，合并两个集合
	tree->s[m2][j] = 0;		// 另一个集全置空
      }
    }
    
    d++;
  }
}

void display(struct tree * tree, int vexter)
{
  int i, j, count;

  count = 0;
  for (i = 1; i <= vertex; i++)
    for (j = 1; j <= vertex; j++) {
      printf(" %d ", tree->s[i][j]);
      count++;
      if (count % vexter == 0) 
	printf("\n");
    }

  printf("\n");
}

void main()
{
  struct tree tree;
  int i;

  for (i = 1; i <= edge; i++) {	// 按从小到大的顺序输入网中的边的起点，终点及权值
    printf("input edge and edge of quan value :\n");
    scanf("%d %d %d", &tree.ge[i].fromvex, &tree.ge[i].endvex, &tree.ge[i].weight);
  }
  
  //display(&tree, vertex);
  kruska(&tree);

  for (i = 1; i < vertex; i++) { 
    printf("fromvex = %d ", tree.c[i].fromvex);
    printf("endvex  = %d ", tree.c[i].endvex);
    printf("weight  = %d ", tree.c[i].weight);
    printf("\n");
  }
}
